package clids.ex1.data_structures;

import java.util.LinkedList;

/**
 * 
 * to add comments to hash set class.
 * 
 * @author Ori Miller
 * 
 */
public class MyHashSet2 {


	private int capacity;  //number of buckets.
	private double up_load_fac;
	private double low_load_fac;
	private int numOfElements;
	private LinkedList[] hs; 

	/**
	 * A default constructor. Constructs a new, empty table with default initial
	 * capacity (16) and load factor (0.75) and lower load factor (0.25).
	 */
	public MyHashSet2() {

		this(16, 0.75, 0.25);
	}

	/**
	 * Constructs a new, empty table with the specified initial capacity and the
	 * specified load factors.
	 * 
	 * @param initialCapacity
	 *            - the initial capacity of the hash table.
	 * @param upperLoadFactor
	 *            - the upper load factor of the hash table.
	 * @param lowerLoadFactor
	 *            - the lower load factor of the hash table.
	 */
	public MyHashSet2(int initialCapacity, double upperLoadFactor, double lowerLoadFactor) {
		
		capacity = initialCapacity;
		up_load_fac = upperLoadFactor;
		low_load_fac = lowerLoadFactor;
		numOfElements = 0;
		hs = new LinkedList[capacity];
	}

	/**
	 * Data constructor - builds the hash set by adding the elements from the
	 * input array one-by-one. If the same value appears twice (or more) in the
	 * list, it is ignored. The new table has the default values of initial
	 * capacity (16), upper load factor (0.75), and lower load factor (0.25).
	 * 
	 * @param data
	 *            Values to add to the set.
	 */
	public MyHashSet2(String[] data) {
		
		//calling the def. constructor, which will init. the table.
		this();

		//adding elements from input array.
		for (int i = 0; i < data.length; i++) {

			add(data[i]);
		}
	}

	/**
	 * Add a new element with value newValue into the table.
	 * 
	 * @param newValue
	 *            new value to add to the table.
	 * @return false iff newValue already exists in the table.
	 */
	public boolean add(String newValue) {
		
		if (contains(newValue)) {
			return false;
		}
		
		int bucket = getBucket(newValue);
		
		if (hs[bucket] == null) {
			hs[bucket] = new LinkedList();
		}

		hs[bucket].add(newValue);
		numOfElements++;
		
		
		double maxLoad = up_load_fac * capacity;
		if (numOfElements > maxLoad) { //we need to increase capacity and re-hash.
			reHash(capacity * 2);
		}
		
		return true;
	}

	/**
	 * Look for an input value in the table.
	 * 
	 * @param searchVal
	 *            value to search for.
	 * @return true iff searchVal is found in the table.
	 */
	public boolean contains(String searchVal) {
		
		int bucket = getBucket(searchVal); 
		LinkedList toSearch = hs[bucket];
		
		if ((toSearch == null) || (!toSearch.contains(searchVal))) {
			return false;   //empty bucket or not existing string.
		}
		
		return true;
	}

	/**
	 * Remove the input element from the table.
	 * 
	 * @param toDelete
	 *            value to delete.
	 * @return true iff toDelete is found and deleted.
	 */
	public boolean delete(String toDelete) {
		
		if (!contains(toDelete)) {
			return false;  //string not found.
		}
		
		int bucket = getBucket(toDelete);
		hs[bucket].remove(toDelete);
		numOfElements--;
		
		double minLoad = low_load_fac * capacity;
		if (numOfElements < minLoad) {  //we need to decrease capacity and re-hash.
			reHash(Math.max((capacity / 2), 1));  //to avoid 0 capacity.
		}
		
		return true;
	}

	
	/**
	 * @return the number of elements in the table.
	 */
	public int size() {
		return numOfElements;
	}

	
	/**
	 * @return the capacity of the table.
	 */
	public int capacity() {
		return capacity;
	}
	
	
	
	/*
	 * helper methods.
	 * 
	 */

	
	/*
	 * gets a string element, and returns a bucket index,
	 * to which it's mapped.  
	 */
	private int getBucket(String str) {
		
		int bucket = str.hashCode() % capacity;
		
		if (bucket < 0) { //we need a positive modulo [0, capacity-1].
			bucket = bucket + capacity;
		}
		
		return bucket;
	}

	/*
	 * gets new capacity of table, and performs a re-hash
	 * (mapping all of the entries to new buckets).
	 */
	private void reHash(int newCapacity) {
		
		capacity = newCapacity;
		
		LinkedList[] old_hs = hs;
		
		hs = new LinkedList[newCapacity]; //the table is now empty.
		numOfElements = 0;
		
		String elem = "";

		//re-hashing.
		for (int i = 0; i < old_hs.length; i++) {
			
			if (old_hs[i] != null) {  //existing bucket.
				for (int j = 0; j < old_hs[i].size(); j++) {
					elem = (String)old_hs[i].get(j);
					add(elem);
				}
			}
		}
	}
}
